﻿using System;
using System.Collections.Generic;
using System.Text;


// 查找
public class Search
{
    // 顺序查找 O(n)
    public int SeqSearch(SeqList<int> sqList, int data)
    {
        for (int i = 0; i < sqList.GetLength(); i++)
        {
            if (data == sqList[i])
            {
                return i;
            }
        }
        return -1;
    }

    // 折半查找 O(logn)
    public int BinarySearch(SeqList<int> sqList, int key)
    {
        int mid = 0;
        int flag = -1;
        int low = 1;
        int high = sqList.GetLength();

        while (low <= high)
        {
            mid = (low + high) / 2;
            if (sqList[mid] == key)
            {
                flag = mid;
                break;
            }
            else if (key < sqList[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        if (flag > 0)
        {
            Console.WriteLine("Search is Successful");
        }
        else
        {
            Console.WriteLine("Search is failing");
        }
        return flag;
    }

    // 二叉排序树查找
    public int SearchByBinaryTree(BiTree<int> bt, int key)
    {
        TreeNode<int> p = null;

        if (bt.IsEmpty() == true)
        {
            Console.WriteLine("The Binary Sorting Tree is empty");
            return 0;
        }

        p = bt.Head;
        while (p != null)
        {
            if (p.Data == key)
            {
                Console.WriteLine("Search is Successful");
                return 1;
            }
            else if (p.Data < key)
            {
                p = p.RChild;
            }
            else
            {
                p = p.LChild;
            }
        }
        return 0;
    }
}
